#include<bits/stdc++.h>
#define int long long
using namespace std;
int P,T,n,m,dp[2][4000005];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline int ksm(int k,int c){
    int a=1,b=k;
    while(c){
        if(c&1) a=(a*b)%P;
        b=(b*b)%P;
        c>>=1;
    }
    return a;
}
inline void add(int &x,int y){
    if((x+y)>=P) x=x+y-P;
    else x+=y;
}
inline void del(int &x,int y){
    if((x-y)<0) x=x-y+P;
    else x-=y;
}
signed main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    P=read(),T=read();
    while(T--){
        n=read(),m=read();
        memset(dp,0,sizeof(dp));
        int inv=ksm(m+1,P-2);
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            int t=i&1;
            for(int j=0;j<=((i-1)*m);j++){
                dp[t][j]=0;
                if(j) add(dp[t^1][j],dp[t^1][j-1]);
            }
            for(int j=0;j<=((i-1)*m);j++){
                int d=(dp[t^1][j]*inv)%P;
                add(dp[t][j],d);
                del(dp[t][j+m+1],d);
            }
        }
        int sum=0,ans=0;
        for(int i=1;i<=(n*m);i++) add(dp[n&1][i],dp[n&1][i-1]);
        for(int i=(n*m);i>=0;i--){
            add(ans,(sum*dp[n&1][i])%P);
            add(sum,dp[n&1][i]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}